import { defaultEquals } from '../utils/utils'
import { Node, INode } from './models/linked-list-models'

export default class LinkedList<T> {
  private count: number
  head: INode<T> | undefined
  equalsFn: (a: T, b: T) => boolean

  constructor(equalsFn = defaultEquals) {
    this.count = 0
    this.head = undefined
    this.equalsFn = equalsFn
  }

  // 向链表尾部添加一个或多个新元素。
  push(element: T | T[]): boolean {
    if (!element) {
      return false
    }
    // 链表空
    let curNode: INode<T> | undefined = undefined
    if (this.isEmpty()) {
      if (element instanceof Array) {
        // 参数是数组
        for (let i = 0; i < element.length; i++) {
          const node = new Node(element[i])
          if (i === 0) {
            this.head = node
            curNode = node
          } else {
            curNode!.next = node
            curNode = node
          }
          this.count++
        }
      } else {
        // 参数是非数组
        this.head = new Node(element)
        this.count++
      }
    } else {
      // 链表非空
      curNode = this.head
      while (curNode!.next !== undefined) {
        curNode = curNode!.next
      } // 此时 curNode 指向链表尾部

      if (element instanceof Array) {
        for (let i = 0; i < element.length; i++) {
          const node = new Node(element[i])
          curNode!.next = node
          curNode = node
          this.count++
        }
      } else {
        curNode!.next = new Node(element)
        this.count++
      }
    }

    return true
  }
  // 向链表的特定位置插入一个多个新元素。
  insert(element: T | T[], position: number): boolean {
    if (
      position < 0 ||
      position > this.size() ||
      (element instanceof Array && element.length === 0)
    ) {
      return false
    }

    let curNode: INode<T> | undefined = undefined
    let oldTailNode: INode<T> | undefined = undefined
    let tempHead: INode<T> | undefined = undefined

    if (this.isEmpty()) {
      // 链表为空
      if (element instanceof Array) {
        for (let i = 0; i < element.length; i++) {
          const node = new Node(element[i])
          if (i === 0) {
            curNode = node
            tempHead = node
          } else {
            curNode!.next = node
            curNode = node
          }
          this.count++
        }
        this.head = tempHead
      } else {
        const node = new Node(element)
        this.head = node
        this.count++
      }
    } else {
      // 链表非空
      oldTailNode = this.head

      // 查找最后一个节点
      while (oldTailNode && oldTailNode.next) {
        oldTailNode = oldTailNode.next
      }

      if (position === 0) {
        // 在链表头部插入
        if (element instanceof Array) {
          for (let i = 0; i < element.length; i++) {
            const node = new Node(element[i])
            if (i === 0) {
              curNode = node
              tempHead = node
            } else {
              curNode!.next = node
              curNode = node
            }
            this.count++
          }
          curNode!.next = this.head // 这里不用考虑链表原来是否空
          this.head = tempHead
        } else {
          const node = new Node(element)
          node.next = this.head
          this.head = node
          this.count++
        }
      } else if (position === this.size()) {
        // 在链表尾部插入

        if (element instanceof Array) {
          for (let i = 0; i < element.length; i++) {
            const node = new Node(element[i])
            if (i === 0) {
              curNode = node
              tempHead = node
            } else {
              curNode!.next = node
              curNode = node
            }
            this.count++
          }
          oldTailNode!.next = tempHead
        } else {
          const node = new Node(element)
          oldTailNode!.next = node
          this.count++
        }
      } else {
        // 在链表中间插入
        let leftNode: INode<T> | undefined = undefined // position - 1
        let rightNode: INode<T> | undefined = undefined // position

        leftNode = this.head

        for (let i = 0; i < position; i++) {
          leftNode = leftNode!.next
        }

        rightNode = leftNode!.next

        if (element instanceof Array) {
          for (let i = 0; i < element.length; i++) {
            const node = new Node(element[i])
            if (i === 0) {
              curNode = node
              tempHead = node
            } else {
              curNode!.next = node
              curNode = node
            }
            this.count++
          }
          leftNode!.next = tempHead
          curNode!.next = rightNode
        } else {
          const node = new Node(element)
          leftNode!.next = node
          node.next = rightNode
          this.count++
        }
      }
    }
    return true
  }
  // 返回链表中特定位置的元素。如果链表中不存在这样的元素，
  // 则返回 undefined。
  getElementAt(index: number): T | undefined {
    if (this.isEmpty() || index < 0 || index >= this.size()) {
      return undefined
    } else {
      let tempNode: Node<T> | undefined = this.head
      let i = 0
      while (i < index) {
        tempNode = tempNode!.next
        i++
      }
      return tempNode!.element
    }
  }
  // 从链表中移除一个元素。
  remove(element: T): boolean {
    if (this.isEmpty()) {
      return false
    } else {
      if (this.head!.element === element) {
        this.head = this.head?.next
        this.count--
        return true
      } else {
        let prevNode: Node<T> | undefined = this.head
        let curNode: Node<T> | undefined = prevNode!.next
        while (curNode) {
          if (curNode.element === element) {
            prevNode!.next = curNode.next
            this.count--
            return true
          } else {
            prevNode = prevNode!.next
            curNode = prevNode!.next
          }
        }
        return false
      }
    }
  }
  // 返回元素在链表中的索引。如果链表中没有该元素则返回-1。
  indexOf(element: T): number {
    if (this.isEmpty()) {
      return -1
    } else {
      if (this.head!.element === element) {
        return 0
      } else {
        let curNode: Node<T> | undefined = this.head
        let i = 0
        while (curNode) {
          if (curNode.element === element) {
            return i
          } else {
            curNode = curNode.next
            i++
          }
        }
        return -1
      }
    }
  }
  // 从链表的特定位置移除一个元素。
  removeAt(position: number): boolean {
    if (this.isEmpty() || position >= this.size()) {
      return false
    } else {
      if (position === 0) {
        this.head = this.head?.next
      } else {
        let curNode: Node<T> | undefined = this.head
        let i = 0
        while (i < position - 1) {
          curNode = curNode?.next
          i++
        }
        if (position === this.size()) {
          curNode!.next = undefined
        } else {
          curNode!.next = curNode!.next?.next
        }
      }
    }
    this.count--
    return true
  }
  // 返回链表包含的元素个数，与数组的 length 属性类似。
  size(): number {
    return this.count
  }
  // 如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false。
  isEmpty(): boolean {
    return this.size() === 0
  }
  // 返回表示整个链表的字符串。由于列表项使用了 Node 类，就需要重写继
  // 承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。
  toString(): string {
    let ret = ''
    let curNode = this.head
    if (!this.isEmpty()) {
      while (curNode) {
        ret += `${curNode.element} `
        curNode = curNode.next
      }
    }
    return ret
  }
}
